import java.util.HashMap;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 九转苍翎
 * Date: 2025/11/16
 * Time: 03:09
 */
public class LRUCache {
    public LinkedNode head;
    public LinkedNode tail;
    public int capacity;
    private int size;
    public HashMap<Integer,LinkedNode> map;

    public LRUCache(int capacity) {
        this.capacity = capacity;
        head = new LinkedNode(0,0);
        tail = new LinkedNode(0,0);
        head.next = tail;
        tail.prev = head;
        this.size = 0;
        this.map = new HashMap<>();
    }

    public int get(int key) {
        if(map.containsKey(key)){
            //从链表中删除该节点
            remove(map.get(key));
            //将该节点头插至链表头部
            headInsert(map.get(key));
            return map.get(key).value;
        }
        return -1;
    }

    public void put(int key, int value) {
        if(map.containsKey(key)){
            //从链表中删除旧节点
            remove(map.get(key));
            //将旧节点从map中删除
            map.remove(key);
        }
        LinkedNode newNode = new LinkedNode(key,value);
        //头插新节点
        headInsert(newNode);
        //将新节点加入map
        map.put(key,newNode);
        if(this.size > this.capacity){
            LinkedNode temp = tail.prev;
            //从链表中删除旧节点
            remove(temp);
            //将旧节点从map中删除
            map.remove(temp.key);
        }
    }

    public void remove(LinkedNode node) {
        LinkedNode prev = node.prev;
        LinkedNode next = node.next;
        prev.next = next;
        next.prev = prev;
        node.next = null;
        node.prev = null;
        this.size--;
    }

    private void headInsert(LinkedNode node) {
        LinkedNode next = head.next;
        head.next = node;
        next.prev = node;
        node.next = next;
        node.prev = head;
        this.size++;
    }

    public static void main(String[] args) {
        LRUCache cache = new LRUCache(2);
        cache.put(1, 1);
        cache.put(2, 2);
        System.out.println(cache.get(1));
        cache.put(3, 3);
        System.out.println(cache.get(2));
    }
}
